import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 马拉圈
 * Date: 2023-05-05
 * Time: 20:58
 */
public class GraphByList {

    static class Node {
        public int src;//起始下标
        public int dest;//目的下标
        public int weigh;//权值
        public Node next;//后继

        public Node(int src, int dest, int weigh) {
            this.src = src;
            this.dest = dest;
            this.weigh = weigh;
        }
    }

    public char[] arrayV;//顶点集合
    public ArrayList<Node> edgeList;//边的集合
    public boolean isDirect;//是否是有向图

    public GraphByList(int size, boolean isDirect) {
        this.arrayV = new char[size];
        edgeList = new ArrayList<>(size);
        //不带参数的话，默认大小为0
        //并且，这只是他的容量是size
        for (int i = 0; i < size; i++) {
            edgeList.add(null);
        }
        this.isDirect = isDirect;
    }

    //初始化顶点数组
    public void initArrayV(char[] chars) {
        for (int i = 0; i < arrayV.length; i++) {
            arrayV[i] = chars[i];
        }
    }

    //获取顶点下标
    public int getIndexOfV(char v) {
        for (int i = 0; i < arrayV.length; i++) {
            if(v == arrayV[i]) {
                return i;
            }
        }
        return -1;
    }


    /**
     * 添加边
     * 这里写的是【出边表】
     * 【入边表】就是倒过来
     * @param v1 起始顶点
     * @param v2 目的顶点
     * @param weight 权值
     */
    public void addEdge(char v1, char v2, int weight) {
        int index1 = getIndexOfV(v1);
        int index2 = getIndexOfV(v2);
        if(index1 != -1 && index2 != -1 && index1 != index2) {
            Node cur = edgeList.get(index1);

            //判断是否存在此边
            while(cur != null) {
                if(cur.dest == index2) {
                    System.out.println("存在此边");
                    return;
                }
                cur = cur.next;
            }
            Node newOne = new Node(index1, index2, weight);
            //【index1 --> index2】
            //头插法插入节点
            newOne.next = edgeList.get(index1);
            edgeList.set(index1, newOne);

            //如果是无向图，相反的边也一并添加
            //如果是无向图，添加操作是联动的，所以上面判断不存在此边
            //此时不用判断
            if(!isDirect) {
                Node node = new Node(index2, index1, weight);
                //【index2 --> index1】
                node.next = edgeList.get(index2);
                edgeList.set(index2, node);
            }
        }

    }
    //打印邻接表
    public void printGraph() {
        for (int i = 0; i < edgeList.size(); i++) {
            Node cur = edgeList.get(i);
            while(cur != null) {
                int index1 = cur.src;
                int index2 = cur.dest;
                System.out.print("[" + arrayV[index1] + "->" + arrayV[index2] + "]");
                cur = cur.next;
            }
            System.out.println();
        }
    }

//获得顶点的度
    public int getDevOfV(char v) {
        int index = getIndexOfV(v);
        int count = 0;
        if (index != -1) {
            Node cur = edgeList.get(index);
            while (cur != null) {
                count++;
                cur = cur.next;
            }
        }
        //如果是有向图
        if (isDirect) {
            int dest = index;
            for (int src = 0; src < edgeList.size(); src++) {
                if (src != dest) {//src == dest 肯定不存在没必要进入
                    Node cur = edgeList.get(src);
                    while (cur != null) {
                        if (cur.dest == dest) {
                            count++;
                        }
                        cur = cur.next;
                    }
                }
            }
        }
        return count;
    }
    //获取所有顶点的入度
    public int[] getDevs() {
        int n = arrayV.length;
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            Node cur = edgeList.get(i);
            while(cur != null) {
                arr[cur.dest]++;
                cur = cur.next;
            }
        }
        return arr;
    }
    public int getFirstZero(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] == 0) {
                return i;
            }
        }
        return -1;
    }
    public void outputV(int index, int[] arr, Queue<Character> queue) {
        queue.offer(arrayV[index]);
        arr[index]--;
        Node cur = edgeList.get(index);
        while(cur != null) {
            arr[cur.dest]--;
            cur = cur.next;
        }
    }
    public boolean isContainCir(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] != -1) {
                return true;
            }
        }
        return false;
    }

    public boolean kahn(Queue<Character> queue) {
        int[] arr = getDevs();
        int index = getFirstZero(arr);
        while(index != -1) {
            outputV(index, arr, queue);
            index = getFirstZero(arr);
        }
        return isContainCir(arr);
    }

    public static void main(String[] args) {


        //定义与构建图
        char[] chars = "012345678".toCharArray();
        GraphByList graph = new GraphByList(chars.length, true);
        graph.initArrayV(chars);
        graph.addEdge('0', '1', 1);
        graph.addEdge('0', '2', 1);
        graph.addEdge('1', '3', 1);
        graph.addEdge('2', '3', 1);
        graph.addEdge('2', '4', 1);
        graph.addEdge('4', '3', 1);
        graph.addEdge('6', '0', 1);
        graph.addEdge('7', '0', 1);
        graph.addEdge('7', '6', 1);
        graph.addEdge('8', '5', 1);

        //定义队列
        Queue<Character> queue = new LinkedList<>();
        boolean flag = graph.kahn(queue);

        System.out.println(flag ? "带环" : "不带环");
        System.out.println(queue);
    }


    public static void main1(String[] args) {
        char[] chars = {'A', 'B', 'C', 'D'};

        GraphByList graph = new GraphByList(chars.length, false);
        graph.initArrayV(chars);
        graph.addEdge('A', 'B', 1);
        graph.addEdge('A', 'D', 1);
        graph.addEdge('B', 'A', 1);
        graph.addEdge('B', 'C', 1);
        graph.addEdge('C', 'B', 1);
        graph.addEdge('C', 'D', 1);
        graph.addEdge('D', 'A', 1);
        graph.addEdge('D', 'C', 1);
        graph.printGraph();
        System.out.println("A节点的度：" + graph.getDevOfV('A'));
        System.out.println("B节点的度：" + graph.getDevOfV('B'));
        System.out.println("C节点的度：" + graph.getDevOfV('C'));
        System.out.println("D节点的度：" + graph.getDevOfV('D'));
    }

}
